package 回溯.不熟;

import java.util.LinkedList;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 将字符串拆分为递减的连续值1849.java
 * @createTime 2023年03月31日 16:28:00
 */
public class 将字符串拆分为递减的连续值1849 {
	public static void main(String[] args) {
		System.out.println(splitString("200100"));
	}

	public static boolean splitString(String s) {
		return backTrace(s.toCharArray(), s.length(), 0, -1, 0);
	}

	public static boolean backTrace(char[] chars, int length, int curIndex, int prev, int num) {
		//结束条件
		if (length == curIndex && num > 1) {
			return true;
		}
		//取数
		int temp = 0;
		for (int i = curIndex; i < length; i++) {
			temp = temp * 10 + (chars[i] - 48);
			//因为是递减第一个开头肯定不能是0
			if (num == 0) {
				if (temp != 0) {
					if (backTrace(chars, length, i + 1, temp, num + 1)) {
						return true;
					}
				}
			} else {
				if (prev == 0) {
					if (i == length - 1) {
						return true;
					}
					continue;
				}
				//小于前数
				if (temp > prev) {
					return false;
				}
				//差超过1，则需要计算下一位
				if (prev - temp > 1) {
					continue;
				}
				//两数之差不为1
				if (prev - temp != 1) {
					return false;
				}
				prev = temp;
				return backTrace(chars, length, i + 1, prev, num + 1);
			}
		}
		return false;
	}
}
